1. Field of the Invention
The present invention relates to a method and apparatus to perform a squaring operation in a finite field.
2. Description of the Related Art
A finite field GF(2n) is a number system containing 2n elements. Based on the fact that each element of the finite field GF(2n) can be represented by n bits, practical applications of the finite field can be accomplished. Practical applications, such as hardware implementation of error correction codes and elliptic curve cryptosystems, frequently perform calculations in GF(2n). An apparatus for encoding/decoding Reed-Solomon codes performs calculations in GF(2n), and an encryption/decryption apparatus of an elliptic curve cryptosystem performs calculations in GF(2n) where “n” is a large value.
The addition and multiplication rules of GF(2), which contain only binary numbers 0 and 1, are defined by Formula (1).0+0=1+1=00+1=1+0=10×0=1×0=0×1=01×1=1  (1)
Here, binary addition is a bitwise exclusive OR (referred to as XOR hereinafter) operation, and binary multiplication is a bitwise AND (referred to as AND hereinafter) operation.
Since the finite field GF(2n) (n>1) is a number system containing 2n elements, addition and multiplication correspond to arithmetic modulo of an irreducible n-degree polynomial having coefficients in GF(2). The irreducible n-degree polynomial is referred to as a defining polynomial of the finite field. When a root of the defining polynomial is α, an element of the finite field has a standard representation given by Formula (2).a0+a1α+a2α2+ . . . +an−1αn−1=(a0,a1,a2, . . . ,an−1),ai∈GF(2)  (2)
Multiplication of two elements in the finite field GF(2n) is given by polynomial multiplication of a and then modulo operation by the defining polynomial. Addition of two elements of the finite field GF(2n) is performed by polynomial addition of α.
Assume that the defining polynomial of the finite field GF(2n) is expressed as shown in Formula (3) and α is a root of the defining polynomial.
                              f          ⁡                      (            x            )                          =                              x            n                    +                                    ∑                              i                =                1                            t                        ⁢                                                  ⁢                          x                              k                i                                              +          1                                    (        3        )            where n is an arbitrary natural number, 0<t, and ki<n.
If an element A of the finite field is expressed as A=(a0,a1,a2, . . . ,an−1)∈GF(2n), the square of the element A is determined by polynomial multiplication of α and then modulo operation by the polynomial f(α).A2≡(a0+a1α+a2α2+ . . . +an−1αn−1)2 mod f(α)  (4)
Conventional techniques of performing a squaring operation as shown in Formula (4) will be explained below. Here, the size of hardware, namely, the number of gates, serves as a measure for area complexity, and gate delays of the hardware serve as a measure for time complexity. Cryptographic standards, such as SEC and ANSI X9.62, define coefficients necessary for the elliptic curve cryptosystems and recommend several coefficients in the finite field. The two standards are most widely used to determine coefficients in the finite field. Accordingly, the two standards are used as criteria in deciding wide applicability of the respective techniques. Here, n represents the dimension of the finite field.
The invention by H. Wu entitled “Bit-parallel finite field multiplier and squarer using polynomial basis (IEEE Transactions on Computers, Vol. 51, No. 7, pp. 750-758, 2002)” discloses an arrangement of squaring results for values of n and k when a defining polynomial is a trinomial given by xn+xk+1. Since the formula adopted by the Wu's invention is optimized, high efficiency in area and time complexity can be achieved. But, Wu's invention does not cover the case when the defining polynomial is a pentanomial.
The invention by C. H. Kim et al. entitled “A new hardware architecture for operations in GF(2n) (IEEE Transactions on Computers, Vol. 51, No. 1, pp. 90-92, 2002)” discloses that when n+1 is a prime number, 2∈Zn+1 is a primitive element in GF(2n), an anomalous basis is used, and a defining polynomial is an all-one polynomial (AOP), squaring can be achieved by rewiring, where rewiring means redefining relationships among elements and/or inserting new elements into a matrix. But, the pertinent n and the defining polynomial for Kim's invention are not found in the standards.
The invention by K. Aoki et al. entitled “Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed (U.S. Pat. Nos. 6,266,688 and 6,202,076, 2001)” discloses that when n is even and the finite field GF(2n) meets a condition of GF(2)<GF(2n/2)<GF(2n), arithmetic operations in the finite field GF(2n) can be performed using arithmetic operations in the finite field GF(2n/2), and suggests a square calculation device using the scheme. But when using the Aoki device, a way of representing the finite field is different from that in the standards, resulting in poor compatibility. Further, since most of “n”s in the standards are odd, the invention by K. Aoki et al. is rarely applicable.
The invention by Lambert et al. entitled “Method and apparatus for implementing arithmetical operations in finite fields (EU Pat. No. 1,076,284 A1, 2001)” performs a squaring operation using a cyclic basis. The cyclic basis is 1,αΔ,α2Δ,α3Δ, . . . ,α(m−1)Δ where Δ, the smallest divisor of 2n−1, satisfies m=(2n−1)/Δ≧n, Δ≧n. In this case, the squaring operation is implemented by rewiring. But the invention requires basis conversion, which is very complex since the factor Δ satisfying the above condition is fairly large.
The invention by G. Orlando et al. entitled “Squaring architecture for GF(2n) and its application in cryptographic systems (Electronics Letters, Vol. 36, No. 13, pp. 1116-1117, 2000)” discloses a method of dividing an element according to predetermined fundamentals and inputting the divided element to a multiplier. The squaring architecture includes 3.5 n gates as well as the multiplier. Accordingly, the invention by G. Orlando et al. is less efficient than the invention by H. Wu employing approximately n/2 gates.
The invention by C. C. Wang et al. entitled “VLSI architectures for computing multiplications and inverses in GF(2m) (IEEE Transactions on Computers, Vol. C-34, No. 8, pp. 709-717, 1985)” utilizes a normal basis such that a squaring operation is implemented by rewiring. But basis conversion required by the invention is very complex.
Accordingly, there is a demand for a method and apparatus for performing a squaring operation that does not require complex basis conversion and has low area and time complexity.